﻿/*
 *  DFUtil - a utility for creating and implementing blueprints in Dwarf Fortress.
 *  
 *  Copyright (C) 2009  Katharine Gillis
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see http://www.gnu.org/licenses/.
*/

using System;
using System.Collections.Generic;
using System.Drawing;

namespace DFUtil
{
    /// <summary>
    /// A static class that runs the Largest Rectangle algorithm.
    /// </summary>
    public static class LargestRectangleAlgorithm
    {
        #region Members

        /// <summary>
        /// Runs the algorithm on the given type of DFItems, in the given list.
        /// </summary>
        /// <param name="items">List of DFItems.</param>
        /// <param name="type">Type of item to run on.</param>
        /// <returns>New list of DFItems containing the largest rectangle as a DFItem, and the DFItems that comprised it removed.</returns>
        public static List<Item> Run(List<Item> items, string type)
        {
            List<Point> points = new List<Point>();
            foreach (Item item in items)
            {
                if (item.Type == type)
                {
                    for (int i = item.Point.X; i < item.Point.X + item.Size.Width; i++)
                    {
                        for (int j = item.Point.Y; j < item.Point.Y + item.Size.Height; j++)
                        {
                            points.Add(new Point(i, j));
                        }
                    }
                }
            }

            List<Item> newItems = new List<Item>();
            Rectangle rect;
            while ((rect = Run(points)) != Rectangle.Empty)
            {
                Item item = new Item(new Point(rect.X, rect.Y), new Size(rect.Width, rect.Height), type);
                newItems.Add(item);
                for (int i = points.Count - 1; i >= 0; i--)
                {
                    Point point = points[i];
                    if (point.X >= rect.X && point.X < rect.X + rect.Width && point.Y >= rect.Y && point.Y < rect.Y + rect.Height)
                    {
                        points.RemoveAt(i);
                    }
                }
            }
            return newItems;
        }

        /// <summary>
        /// Runs the algorithm on a set of points, returning a rectangle representing the largest rectangle made up of those points.
        /// </summary>
        /// <param name="points">List of points.</param>
        /// <returns>Largest rectangle.</returns>
        public static Rectangle Run(List<Point> points)
        {
            Point best_ll = new Point(0, 0);
            Point best_ur = new Point(-1, -1);
            int M = 0;
            int N = 0;
            int m = 0;
            int n = 0;
            foreach (Point p in points)
            {
                if (p.X > N)
                    N = p.X;
                else if (p.X < n)
                    n = p.X;
                if (p.Y > M)
                    M = p.Y;
                else if (p.Y < m)
                    m = p.Y;
            }
            N++;
            M++;

            int[] cache = new int[M-m];
            for (int i = 0; i < M-m; i++)
            {
                cache[i] = 0;
            }

            Point ll = new Point(N-1, 0);
            while (ll.X >= n)
            {
                cache = UpdateCache(ll.X, cache, points, M, m);
                ll.Y = m;
                while (ll.Y < M)
                {
                    Point ur = GrowOnes(ll, cache, M, m, N);
                    if (Area(ll, ur) > Area(best_ll, best_ur))
                    {
                        best_ll = ll;
                        best_ur = ur;
                    }
                    ll.Y++;
                }
                ll.X--;
            }

            if (Area(best_ll, best_ur) > 0)
                return new Rectangle(new Point(best_ll.X, best_ll.Y), new Size(best_ur.X - best_ll.X + 1, best_ur.Y - best_ll.Y + 1));
            else
                return Rectangle.Empty;
        }

        #endregion

        #region Private members

        // Updates the cache of points along the y axis.
        private static int[] UpdateCache(int x, int[] cache, List<Point> points, int M, int m)
        {
            for (int y = m; y < M; y++)
            {
                if (points.Contains(new Point(x, y)))
                    cache[y-m]++;
                else
                    cache[y-m] = 0;
            }
            return cache;
        }

        // Determines the largest number of ones along the y axis and x axis (already scanned).
        private static Point GrowOnes(Point ll, int[] cache, int M, int m, int N)
        {
            Point ur = new Point(ll.X - 1, ll.Y - 1);
            int x_max = N;
            int y = ll.Y - 1;
            while (y + 1 < M && cache[y + 1 - m] != 0)
            {
                y++;
                int x = Math.Min(ll.X + cache[y - m] - 1, x_max);
                x_max = x;
                if (Area(ll, new Point(x, y)) > Area(ll, ur))
                    ur = new Point(x, y);
            }
            return ur;
        }

        // Calculates the area of the rectangle defined by the two points.
        private static int Area(Point ll, Point ur)
        {
            if (ll.X > ur.X || ll.Y > ur.Y)
                return 0;
            else
                return (ur.X - ll.X + 1) * (ur.Y - ll.Y + 1);
        }

        #endregion
    }
}
